1. Field of the Invention
This invention relates generally to methods and apparatus for converting electronically stored image data in outline form into a bitmap form which can be used to drive a dot matrix output device. More particularly, the present invention relates to an improved method and apparatus for converting input image data from a graphical/mathematical format to a display or print device format (i.e. a series of dots/pixels), wherein said method implements an outline font rendering process that provides scaling, scan-conversion, and shape filling of characters/graphics in spline outline formats. The method can be applied to a variety of font data input formats.
2. Description of the Prior Art
The outline font rendering process represents a large computational load and limits the performance of laser printer systems. More specifically, since the outline font rendering process must maintain typographic quality of an input font during font scaling and rotation as related to the limited resolution (typically 300 dots per inch) of a laser printer, a very slow printing rate/per page results.
A prior art outline font rendering process involves the following steps:
(1) Retrieving an outline font source data from a source of font character, wherein the character defines the outline of the source data with a set of curve and line control points. PA0 (2) Transforming the source data in high precision to a set of control points (i.e., a transform image) related to a new coordinate system, wherein the same data is rotated and scaled accordingly. PA0 (3) Correcting the transform image for misalignment by rounding its boundaries either up or down to the lowest quantized value of the new coordinate system. The output from this step is a corrected transformed image. Furthermore, the corrected transformed image is adjusted (according to the hints included with the curves and lines of the source data) to eliminate image distortions due to grid correction. PA0 (4) Scan-converting the corrected transform image to a sequence of points occurring at periodic intervals along the outline of the image. This sequence of points is an image outline. PA0 (5) Selectively filling the image outline with points to provide a solid representation of the image in bitmap form. PA0 (6) Processing the resulting filled outline of the image by a raster operator, which produces a stream of data.
An outline font source data is made up of a set of control points of curves and lines which serve to define the outline of the source data. Referring now to FIG. 1 which illustrates the composition of the outline font source data of a small letter "a", the figure is shown on a pixel grid blown up many times normal size in order to see the details of the original curves 10 and the short vector approximation to the curves 20. The arrows 30 show the order in which the curves are processed.
FIG. 2 shows an enlarged simple curve composed of straight lines and cubic Bezier curves. A straight line segment may be defined by two points: a start point 40 and an end point 42. A cubic Bezier curve is defined by four points: a start point 42, a first control point 44, a second control point 46, and an end point 48. The start and end points always lie on the curve.
FIG. 3 shows the same curve as FIG. 2 but rendered as quadratic B-Spline curves and straight lines. As before, straight lines are defined by a begin point 50 and an end point 52, both of which lie on the line. A quadratic B-Spline curve is defined by three control points but the control points come in two weights. Off-curve control points have a weight of "one", while on-curve control points have a weight of "two". The weight indicates how many times the point is used in developing curves of the contour. The first curve after the line segment is defined by the on-curve point at the end of the line segment 52 and the off-curve control point 54 so the three points that define the first curve are 52, 52, 54. The second curve is defined by the points 52, 54, 56, and the third curve is defined by 54, 56, 56. The process can be visualized as making a list of the control points with on-curve entries repeated, then taking groups of three entries to define a curve as follows: (Note that each vertical row of X's represents one defined curve.)
______________________________________ 52 (on) X 52 (on) X X 54 (off) X X X 56 (on) X X X 56 (on) X X X 58 (off) X X X 59 (on) X X 59 (on) X ______________________________________
One problem in prior art devices is the transfer of redundant control point data. As discussed earlier, an outline font is made up of a set of curves or lines wherein each curve or line is made up of control points. When a curve of the outline font is processed all the control points associated with that curve must be transferred to the processing device. In many cases a control point is applicable to two curves, thus redundant data transfer occurs.
Scan-conversion is the process of selecting the pattern of device pixel dots which match the mathematical representation of the image outline to be displayed. FIG. 4 demonstrates one method of defining a set of transition points based on a pixel centered scan line 60. A transition is defined as a change of state along the scan line. That is, when a scan line crosses the outline of the character the "insidedness" of a point on the scan line changes going from outside to inside or inside to outside. Thus a transition is created each time one of the short vectors crosses the vertical centerline of a pixel for horizontal scanning.
The final placement of the transition is a function of first the pixel level rules for placement (e.g., transition detection with offset) and secondarily the character level rules (e.g., rules dealing with multiple transitions in a single pixel and handling image enhancement). FIG. 4 illustrates an example of a pixel level rule of transition detection and placement, the so-called 50-50 rule. If the point of intercept 62 with the horizontal scan line 60 placed at the vertical middle of the pixel occurs to the left of the horizontal center then the transition 64 will be assigned to the pixel in which the crossing took place. If the point of intercept 66 crosses on or to the right of the pixel center the transition 68 will be assigned to the pixel to the right of that which contains the intercept.
Most of the prior art devices and methods adapt the Bresenham algorithm for the scan-conversion process. Bresenham algorithms are described in the articles: (1) "Algorithm for Computer Control of a Digital Plotter," IBM System Journal, Vol.4, No.1, 1965, by J. E. Bresenham, (2) "A Linear Algorithm for Incremental Digital Display of Circular Arcs," Communication of the ACM, February, 1977, p.100-106, by J. E. Bresenham.
A problem with the prior art methods of scan conversion is that an independent and unique scan conversion method must be used for the different formats chosen by different typographic designers to store their type designs. That is, a different scan converter method must be used for vectors, arcs, Beziers, and B-spline. It is much more desirable for a commercial product to use one general set of scan-conversion and filling methods that can handle the various available font standards, rather than to use several independent methods for different formats.
Filling is the process of turning on device pixel dots which fall within the interior area bounded by the outline pixel dots generated from the scan-conversion process. There are two major filling algorithms found in the prior art: Even-Odd parity fill and Non-Zero Winding fill. FIG. 5 illustrates the even-odd parity fill algorithm along with the 50-50 transition detection rules.
Starting at the far left a value of "0" (outside or white) is assumed and maintained until the first transition 90 is encountered. At this point a value of "1" (inside or black) is assigned and maintained until the next transition 74 is encountered. The run of "1"s between "0"s is a horizontal span or fill for the character, in this case running from the first transition 70 to one before the second transition 74. The Even-Odd parity fill algorithm assumes that the character being processed contains no overlapping contours which were supposed to receive solid fill.
An alternate filling algorithm is "Non-Zero Winding". This method assigns a value to each transition based on the sign of the Y component of the segment which created it. That is, a "+1" is assigned if the segment is horizontal or rises going from the segment's starting point to its endpoint, a "-1" is assigned if the segment is going down. If no transition occurs at a point it is considered "0". To create the filled character the line is scanned from left to right starting with a value of zero and a sum is kept of the assigned transition values. A "1" (inside or black) is assigned to each point on the scan line where the sum is not zero. Thus, returning to FIG. 4, the first transition 68 would be assigned -1 because its segment is going down along the path being traced. The second transition 64 is assigned a +1 because its segment is going up. When the filling process is applied, returning to FIG. 5, the sum starts at "0" so the fill is left at zero until the first transition. The first transition has a value of -1, thus the sum is -1 (non zero) and the fill is set to "1". The next transition is assigned +1 so the sum is "0" and the fill is set to "0". For this case the result is identical to the result of the Even-Odd filling.
Referring now to FIG. 6 which illustrates a shortcoming of the Even-Odd parity fill algorithm, the figure depicts two overlapping contours, a horizontal rectangle 76, and a vertical rectangle 78 crossed to form a "+" character. When the character is filled with the Even-Odd parity fill algorithm, it is left with a hole in the center of the character. FIG. 7 depicts the same character filled using the Non-Zero Winding fill algorithm. The direction of tracing both the horizontal 90 and the vertical 91 contour is marked by arrows 92. A scan line 93 passing through the area of interest encounters a first transition 94 assigned with a -1, the second transition 95 is also assigned a -1, the third transition 96 is assigned +1, and the fourth 97 is assigned +1. The sum at the first transition is -1, at the second is -2, at the third is -1 and at the fourth is 0, thus between the first and fourth transition positions the fill is "1" continuously.
Hawes (U.S. Pat. No. 4,745,575) discloses a technique to accomplish area filling using hardware. A microprocessor performs the Bresenham algorithm of scan-conversion. Polysegments generated by the scan-conversion microprocessor are then fed to a hardware filling module. Hawes uses a single auxiliary memory to store the outline of a polygon area, and the Filling Starting Point and Filling Ending Point information for all the horizontal filling spans involved in the scan-converted polygons. Since the design is based on the integer Bresenham algorithm, it suffers a quality problem when it is applied to render outline fonts.
A scientific paper entitled "Vertical Scan-Conversion for Filing Purposes" by R. D. Hersch (Proceeding Computer Graphics International 88, Geneva, Springer Verlag, 1988), reports on studies of scan-conversion methods and describes a method for solving the incompatibility issue of scan-conversion and filling approaches. Splines are subdivided into variable lengths of polysegments which can have non-integer vertices. From intersections between the polysegments and scan lines, the algorithm determines two transition pixels for each horizontal span as the beginning and ending indicators. Each transition pixel indicates a color change, from black to white, or vice versa. Between the two transition pixels are interior pixels which are filled by applying a "parity scan line fill method." In order to calculate the intersection and locate the transition pixels, a time-consuming geometrical computation is performed. The higher the resolution, the more calculations are involved. Since the method uses the Even-Odd parity filling algorithm, the problem dealing with overlapping contours (discussed earlier) OCCURS.
Lien (U.S. Pat. No. 4,855,935) discloses a technique to scan-convert curves and vectors by the hardware implementation of Adaptive Forward Difference (AFD) algorithm. Lien adapts the Forward Difference parameter increment so as to advance along the curve with a step size which is approximately equal to the distance between two adjacent pixels. This method is called "Adaptive Forward Difference (AFD)." Thus, in the Lien apparatus, curves and curved surfaces are rendered by AFD and vectors are rendered by Bresenham algorithm using many of the same circuit components utilized by AFD. Since the AFD algorithm does not require the high speed stack memory, it is more suitable for being implemented in the hardware apparatus.
Hassett (U.S. Pat. No. 4,937,761) discloses a technique for rendering outline fonts using hardware. In the Hassett device, a line or curve is scan-converted ("discrete point conversion" in Hassett's terminology) to polysegments. Then the polysegments are further transformed to the coordinate resolution of the target marking engine. Scaling up or down operations may be applied to the polysegments during the "transforming" process. Hassett also uses a dithering technique to smooth the polysegments which are further scan-converted during the "transforming" step. The final scan-converted and dithered polysegments are separated as a dithered image outline shape and a map of interior pixels to be filled, which are then combined for receipt by the raster operator. Two separated memories are required to store the outline points and filling starting point/filling ending points. The final bitmap image is provided by combining the outline image and the filled image resulting from parity filling all the starting points/ending points. Since the object outline is generated by the conventional scan-conversion algorithm (the Bresenham algorithm is used), the dithering technique is used instead of "hinting" to improve the bitmap image quality in Hassett's approach.
Another problem with the prior art method of hinting is that it is based at the character level. Character level hints require intensive processing which must be performed before any other image processing can be accomplished. Thus, hinting at the character level decreases the throughput of an outline font rendering system.
Still another problem with prior art devices is that the entire image is converted to bitmap format. This increases the memory requirements and decreases the throughput of these prior art font rendering systems.